﻿package list;

import java.util.Stack;

import common.Node;

public class 两个链表相加 {
	public static void main(String[] args) {

	}

	public static Node addList1(Node head1, Node head2) {
		Stack<Integer> stack1 = new Stack<>();
		Stack<Integer> stack2 = new Stack<>();

		while (head1 != null) {
			stack1.push(head1.value);
			head1 = head1.next;
		}
		while (head2 != null) {
			stack2.push(head2.value);
			head2 = head2.next;
		}
		int ca = 0;// 表示进位
		int n1 = 0;
		int n2 = 0;
		int n = 0;
		Node node = null;
		Node pre = null;
		while (!stack1.isEmpty() || !stack2.isEmpty()) {
			n1 = stack1.isEmpty() ? 0 : stack1.pop();
			n2 = stack2.isEmpty() ? 0 : stack2.pop();
			n = n1 + n2 + ca;
			pre = node;
			node = new Node(n % 10);
			node.next = pre;
			ca = n / 10;
		}
		if (ca == 1) {
			pre = node;
			node = new Node(1);
			node.next = pre;

		}
		return node;
	}

	public static Node addList2(Node head1, Node head2) {
		head1 = reverse(head1);
		head2 = reverse(head2);
		int n = 0;
		int n1 = 0;
		int n2 = 0;
		int ca = 0;

		Node c1 = head1;
		Node c2 = head2;
		Node node = null;
		Node pre = null;
		while (c1 != null || head2 != null) {
			n1 = c1 == null ? 0 : c1.value;
			n2 = c1 == null ? 0 : c1.value;
			n = n1 + n2 + ca;
			ca = n / 10;
			pre = node;
			node = new Node(n % 10);
			node.next = pre;
			c1 = c1.next != null ? c1.next : null;
			c2 = c2.next != null ? c2.next : null;
		}
		if (ca == 1) {
			pre = node;
			node = new Node(1);
			node.next = pre;
		}
		reverse(head1);
		reverse(head2);
		return node;
	}

	public static Node reverse(Node head) {
		Node pre = null;
		Node hnext = null;
		while (head != null) {
			hnext = head.next;// 用老保存head->next
			head.next = pre;
			pre = head;
			head = hnext;
		}
		return head;
	}
}
